#pragma once
#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

template <typename T>
class BinarySearchTree
{
public:
	BinarySearchTree();
	BinarySearchTree(const BinarySearchTree& rhs);
	BinarySearchTree(BinarySearchTree&& rhs);
	~BinarySearchTree();

	const T& findMax() const {
		return findMax(root);
	}
	const T& findMin() const;

	bool contains(const T& x) const {
		return contains(x, root);
	}
	bool isEmpty() const;
	void printTree(ostream & out = cout) const;

	void makeEmpty() {
		makeEmpty(root);
	}
	void insert(const T& x) {
		inert(x, root);
	}
	void insert(T&& x) {
		insert(std::move(x), root);
	}
	void remove(const T& x) {
		remove(x, root);
	}

	BinarySearchTree& operator=(const BinarySearchTree& rhs);
	BinarySearchTree& operator=(BinarySearchTree&& rhs);

private:
	struct BinaryNode
	{
		T node;
		BinaryNode * leftChild;
		BinaryNode * rightChild;

		BinaryNode(const T& node, BinaryNode* left, BinaryNode* right) :
			this.node{ node }, leftChild{ left }, rightChild{ right } {}
		BinaryNode(T&& node, BinaryNode* left, BinaryNode* right) :
			this.node{ std::move(node) }, leftChild{ left }, rightChild{ right } {}
	};
	BinaryNode* root;

	void insert(const T& x, BinaryNode*& node) {
		if (node == nullptr) {
			node = new BinaryNode(x, nullptr, nullptr);
		}
		else if (x < node->this.node) {
			insert(x, node->leftChild);
		}
		else if (x > node->this.node) {
			insert(x, node->rightChild);
		}
		else;
	}

	void insert(T&& x, BinaryNode*& node) {
		if (node == nullptr) {
			node = new BinaryNode(std::move(x), nullptr, nullptr);
		}
		else if (std::move(x) < node->this.node) {
			insert(std::move(x), node->leftChild);
		}
		else if (std::move(x) > node->this.node) {
			insert(std::move(x), node->rightChild);
		}
		else;
	}
	void remove(T& x, BinaryNode*& node);

	BinaryNode* findMax(BinaryNode* node) const {
		if (node == nullptr) return nullptr;
		if (node->rightChild == nullptr) return node;
		findMax(node->rightChild);
	}

	BinaryNode* findMin(BinaryNode* node) const {
		if (node == nullptr) return nullptr;
		if (node->leftChild == nullptr) return node;
		findMin(node->leftChild);
		/*else {
			while (node->leftChild != nullptr) {
				node = node->leftChild;
			}
			return node->this.node;
		}*/
	}

	bool contains(const T& x, BinaryNode* node) const {
		if (node == nullptr) {
			return false;
		}
		else if (x < node->this.node) {
			return contains(x, node->leftChild);
		}
		else if (x > node->this.node) {
			return contains(x, node->rightChild);
		}
		else {
			return true;
		}
	}
	void makeEmpty(BinaryNode*& node) {
		if (node != nullptr) {
			makeEmpty(node->leftChild);
			makeEmpty(node->rightChild);
			delete node;
		}
		node = nullptr;
	}

	void printTree(BinaryNode* node, ostream& out) const;
	BinaryNode* clone(BinaryNode* node) const {
		if (node == nullptr) {
			return nullptr;
		}
		else {
			return new BinaryNode(node->this.node, clone(node->leftChild), clone(t->rightChild));
		}
	}
};

template<typename T>
BinarySearchTree::BinarySearchTree(const BinarySearchTree& rhs) :root{ nullptr } {
	root = clone(rhs.root);
}

template<typename T>
BinarySearchTree::~BinarySearchTree() {
	makeEmpty();
}
#endif